1. Field of the Invention
This invention relates to the specific area of computer technology associated with the data structures useful in networking tasks. More specifically, it relates to dynamic data structures having the capability of adding large numbers of active file entries to data tables or deleting such file entries from these tables.
2. Discussion of Related Art
To assist in the understanding of the present invention and related art, the following abbreviations and acronyms are defined as follows:
Active Session—data entry being sought in a data structure containing data associated with a session that is currently sending and receiving packets.
Chained pointers—pointers within data objects that create a linked list of such objects.
Data structure—grouping of related table entries
DT—direct table
FIN—finish
FM—full match
FQ—free queue
Hashing—reducing the network portion of an address to a manageable index
MAC—media access control
Patricia tree—A table structure associated with binary searching techniques wherein all address strings and accompanying information are stored in a binary tree
PSCB—pattern search control block
TCB—timer control block
Many commonly used networking tasks are organized by structuring various data bases (i.e. routing tables, active session state, etc.). Hash tables are often used with various mechanisms for resolving the case of multiple entries hashing to the same location (i.e. Patricia tree via chained pointers or “pattern search control blocks” (PSCBs) to the desired entry). Organization and maintenance of these data structures vary significantly according to the associated applications. In a first class, many of these data structures are static (at least when viewed over a short period of time), and are updated by a network administrator only in response to occasional network configuration changes, if at all. In a second class, routing tables may be updated based on communications with other routers in the network. There is a third class of data structures. These data structures may be characterized as dynamic, responding to normal data traffic by adding entries useful in processing subsequent traffic sharing some specific characteristics. Examples of such data structures include layer 2 MAC address tables used in bridging functions, and various session-based data structures. Since a session entry is kept only as long as a session is active, session-based structures are likely the most dynamic and, therefore, create the biggest challenge.
One specific challenge with dynamic tables is that these data structures will eventually get full. Even if there are basic procedures (i.e. detection of the end of a session) to remove obsolete entries, an occasional missing packet can cause these data bases to grow without bound, eventually overflowing available memory. A standard technique for controlling the total number of entries is to apply various aging or timer functions to active entries. These mechanisms test each active entry periodically to determine how long it has been since it was last used.
FIG. 1 illustrates a basic data structure capable of providing an aging or timer function. This data structure is based on a full match (FM) hash table algorithm described separately in said related patent application U.S. Ser. No. 09/543,531. This structure consists of a direct table (DT) 100 to which a hashed search key 102 is applied, with a tree structure 104 of pointers to resolve collisions in each DT entry. For a given search key, a chain of pointers called pattern search control blocks or PSCBs 106 in the tree structure will lead from the DT to the desired data, shown in the Figure as “active sessions” 108. Note that all active sessions are linked together in a loop, enabling a timer or aging function to step through all active sessions sequentially, looking for entries that have outlived their usefulness. This aging function not only points to the next active session 140 to test, but also controls the insertion point for new sessions and the deletion point for obsolete sessions. As required, a new session is established by moving an entry from the head 110 of the free queue 116 to the rope pointer insertion/deletion point 112 in the main tree structure 104. Likewise, an obsolete session is moved from the insertion/deletion point in the main structure 104 to the tail 114 of the free queue 116.
The data structure of FIG. 1 has usefulness in applications requiring random session deletes based on packet traffic being processed. For example, if a finish (FIN) message is detected for a specific session, the corresponding session may be marked for deletion, but the memory resource for that session is not be returned to the free queue until the aging pointer is advanced to this entry. This protocol results in numerous obsolete entries in the data structure that are waiting for the aging process to catch up, and thus limits the memory resources available for active entries. As a result, significant limitations are created in applications requiring both very large and very dynamic data structures.
FIG. 2 illustrates a related art alternative to the structure described in FIG. 1, and uses a double linked list in the timing or aging loop. This data structure consists of a direct table (DT) 200 to which a hashed search key 202 is applied, with a tree structure 204 of pointers to resolve collisions in each DT entry. For a given search key, a chain of pointers, PSCBs 206 in the tree structure, lead from the DT to the active sessions 208. The double linked list enables a random delete to be processed immediately, since a given session entry contains pointers to both the session in front of it and the session behind it. As with FIG. 1, new sessions 240 are established by moving an entry from the head 210 of the free queue 216 to the rope pointer insertion/deletion point 212 in the main structure 204. In order to handle the possibility of missing an explicit request to delete a session, obsolete sessions may be aged out by moving them from the insertion/deletion point 212 in the main structure 204 to the tail 214 of the free queue 216. Thus, an obsolete session can immediately be removed from the timing/aging loop and returned to the free queue 216 for use by a subsequent new session.
This procedure solves the memory resource problem, but may create a performance problem for highly dynamic data structures due to the significant increase in memory accesses. In order to remove an entry from the double linked chain, three entries must be read, modified and written back. An additional entry must be read and written back to place the deleted entry on the free queue. A similar process is required for insertions of new sessions. For high rates of insertions and deletions, this can create a significant contention for access to memory resources. This contention not only increases latency for insertions and deletions, but affects normal packet processing as well, since normal packet processing contends for the same memory resources and encounters increased queuing delays due to the shared access.
One additional deficiency with the structures of both FIG. 1 and FIG. 2 relates to the accuracy of any implemented timer function. Typically, when a timer is started (or restarted), a timeout value is added to a time stamp in real-time and is written to the session entry. Then a timer support process examines each entry in the sequence determined by the loop of chained pointers, comparing the timer entry with the current time-stamp value. When a new packet is processed for a given session, its timer is restarted, resulting in a random distribution of time-out values in the loop. Then, in the worst case scenario, the timer support process may have to test every entry in the loop between the time the timer of a specific session actually expires and the time the session is actually tested. For a large data structure (e.g. 1 million entries), this could take hundreds of milliseconds. Conversely, the timer or aging process may have to read and test a given session entry for time-out multiple times before the timer actually expires, adding to the bandwidth utilization of the memory bus, and resulting in a corresponding increase in contention for access to that memory resource.
Some of these problems are overcome with the related art embodiment shown in FIG. 3. This figure illustrates an embodiment of the related invention described in Invention Disclosure RAL9-1999-0139. In mapping from a hashed search key (not shown) to a corresponding active session entry, this data structure uses the same direct table 300 and pattern search control block structure 304 illustrated in FIG. 1. The most significant difference is that the free queue 316 is merged with active sessions 308 into a larger timing loop 320. This simplifies insertions and deletions significantly, since there is no longer a requirement to rechain the session entry. A deletion simply detaches the PSCB and allows the obsolete entry to flow into the free queue section 316 of the loop. An insertion simply requires an advancement of the free queue head pointer 310 and modification of the tree structure to connect a PSCB 306 to the new session entry 340. Also different is the use of a spare buffer pool 322 to add and remove buffers from the loop at 324 to maintain delays.